//
//  Problem1855.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/18.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1855. 下标对中的最大距离
 给你两个 非递增 的整数数组 nums1​​​​​​ 和 nums2​​​​​​ ，数组下标均 从 0 开始 计数。

 下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i​​ 。

 返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

 一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。

 示例 1：
     输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
     输出：2
     解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
     最大距离是 2 ，对应下标对 (2,4) 。
 示例 2：
     输入：nums1 = [2,2,2], nums2 = [10,10,1]
     输出：1
     解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
     最大距离是 1 ，对应下标对 (0,1) 。
 示例 3：
     输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
     输出：2
     解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
     最大距离是 2 ，对应下标对 (2,4) 。
 示例 4：
     输入：nums1 = [5,4], nums2 = [3,2]
     输出：0
     解释：不存在有效下标对，所以返回 0 。
  

 提示：
     1 <= nums1.length <= 105
     1 <= nums2.length <= 105
     1 <= nums1[i], nums2[j] <= 105
     nums1 和 nums2 都是 非递增 数组
 */
@objcMembers class Problem1855: NSObject {
    func solution() {
        print(maxDistancePoint([55,30,5,4,2], [100,20,10,10,5]))
        print(maxDistancePoint([2,2,2], [10,10,1]))
        print(maxDistancePoint([30,29,19,5], [25,25,25,25,25]))
        print(maxDistancePoint([5,4], [3,2]))
    }
    
    /*
     n * (logm)
     二分法
     遍历数组nums1，找到n[i]在nums2的中刚刚比n1大的最小值, 进行计算
     */
    func maxDistance(_ nums1: [Int], _ nums2: [Int]) -> Int {
        var result: Int = 0
        var left = 0
        var right = 0
        var mid = 0
        for (i, n1) in nums1.enumerated() {
            if n1 > nums2.first! {
                continue
            }
            left = right
            right = nums2.count-1
            while left <= right {
                mid = (left + right) / 2
                if nums2[mid] >= n1 {
                    left  = mid + 1
                } else {
                    right = mid - 1
                }
            }
            if right < i {
                continue
            }
            
            result = max(abs(i - right), result)
            print(i, right)
        }
        return result
    }
    
    /*
     n+m
     双指针：
     1: 创建2个指针，指向2个数组的右侧， left，right
     2: 当n1[left] <= n2[right] && left <= right，满足条件,计算，然后left-=1
     3: n1[left] > n2[right]: right -= 1
     */
    func maxDistancePoint(_ nums1: [Int], _ nums2: [Int]) -> Int {
        var result: Int = 0
        var left  = nums1.count - 1
        var right = nums2.count - 1
        
        while left >= 0, right >= 0 {
            if nums1[left] <= nums2[right] {
                if left <= right {
                    result = max(result, right - left)
                }
                left -= 1
            } else {
                right -= 1
            }
        }
        return result
    }
}
